class Solution(object):
    def subStrHash(self, s, power, modulo, k, hashValue):
        value = 0
        n = len(s)
        nums = [ord(c) - ord('a') + 1 for c in s]
        for i in range(1, k + 1):
            value = (value + nums[-i] * pow(power, k - i, modulo)) % modulo
        if value == hashValue:
            r_value = s[-k:]
        for i in range(n - k):
            value = ((value - nums[n - 1 - i] * pow(power, k - 1, modulo)) * power + nums[n - 1 - i - k]) % modulo
            if value == hashValue:
                r_value = s[n - 1 - i - k: n - 1 - i]
        return r_value

data = Solution()
print(data.subStrHash('leetcode', 7, 20, 2, 0))
